<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,a4paper,french]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage{a4}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
\usepackage[dvips]{graphics}
\usepackage{epsfig}
\usepackage{calc}
\usepackage{tabls}
\usepackage{slashbox}
\usepackage{times}
\usepackage{tabularx}
\usepackage{textcomp}
\usepackage{pst-all}
\usepackage[a4paper]{geometry}
\input{symboles.sty}


\date{}
\geometry{hmargin=1cm, vmargin=1.5cm}\begin{document}
\title{
DÃ©partement d'informatique.\\
Partiel de  mathÃ©matiques discrÃ¨tes. \\  
Semestre 2 (Novembre 09)\\ 
}
\maketitle

Aucun document autorisÃ©. 

\begin{tabular}{ll}
Nom: &amp;......................................... \\
PrÃ©nom: &amp;.........................................\\ 
\end{tabular}
\section{QCM}
Cette partie contient 30 affirmations. Vous aurez +1 Ã&nbsp; chaque valeur de vÃ©ritÃ© trouvÃ©e, -1 Ã&nbsp; chaque erreur (et 0 en absence de rÃ©ponse). Les notes seront ajustÃ©es Ã&nbsp; l'intervalle $[0;20]$ (les notes nÃ©gatives auront 0).\\ 

Q. 1. Soit la dÃ©monstration  syntaxique suivante: \newline
\begin{center}
\begin{tabular}{lll}
\multicolumn{3}{l}{DÃ©monstration sous hypothÃ¨ses 
$\{\neg B \Rightarrow \neg A, A\}$}\\
1.&amp;$\neg B \Rightarrow \neg A$ &amp;$H_1$ \\
2.&amp;$A$ &amp;$H_2$ \\
3.&amp;\_\_\_\_\_ &amp; \_\_\_\_\_ \\
4.&amp;\_\_\_\_\_ &amp;\_\_\_\_\_ \\
5.&amp;$\neg\neg B$ &amp;rÃ©duction de l'absurde entre 4. et 1. \\
6.&amp; $ \neg \neg B \Rightarrow B $&amp;Axiome 9 ($B/P$).\\
7.&amp; $B$ &amp;mp entre 5. et 6. \\
Conclusion

\end{tabular}
\end{center}

\noindent La dÃ©monstration est correcte si en 3. et 4. on a: 
\begin{tabular}{lll}
3.&amp;$A \Rightarrow (\neg B \Rightarrow A)$ &amp;Axiome 1 ($A/P,\neg B /Q$). \\
4.&amp;$\neg B \Rightarrow A $ &amp;modus ponens entre 2. et 3.
\end{tabular}
\\ 

Q. 2. \og $A$ Ã&nbsp; moins que  $B$ \fg{}
peut-elle Ãªtre reprÃ©sentÃ©e par $ \neg A \Rightarrow B$?
	\\ 

Q. 3.  La nÃ©gation de \og ce triangle est rectangle donc ce triangle possÃ¨de un angle droit \fg{}
est-elle  \og ce triangle ne possÃ¨de pas un angle droit et pourtant il est rectangle\fg{}
	\\ 

Q. 4. Soit $p$ et $q$ les variables propositionnelles correspondant respectivement Ã&nbsp; \og il est grand \fg{} et \og il est beau \fg{}.
	Sachant que \og il  est petit \fg{} signifie qu'il n'est pas grand,
\og il est grand ou il est petit et beau \fg{} peut-elle s'Ã©crire
$ p \lor q $?
	\\ 

Q. 5. 
\og Il est faux qu'il ne fait pas froid ou qu'il pleut \fg{}
est-elle Ã©quivalente Ã&nbsp;   \og il fait froid mais il ne pleut pas \fg{}?
	\\ 

Q. 6.  Soit $p$, $q$, $r$ trois variables propostionnelles.
	L'Ã©noncÃ© suivant est-il une tautologie?
$
(p \Rightarrow q) \land (p \lor r) \Rightarrow q \lor r$.
	\\ 

Q. 7. Une formule propositionnelle $F$ est  consÃ©quence logique d'une antilogie.
	 L'affirmation suivante est-elle vraie:
\og  $F$ est donc une tautologie \fg{}?
        \\ 

Q. 8. Soit $p$ et $q$ les variables propositionnelles correspondant respectivement Ã&nbsp; \og il est grand \fg{} et \og il est beau \fg{}.
	Sachant que \og il  est petit \fg{} signifie qu'il n'est pas grand,
\og il est grand ou il est petit et beau \fg{} peut-elle s'Ã©crire
$ (p \lor \neg p) \land q $?
	\\ 

Q. 9.  Soit $p$, $q$, $r$ trois variables propostionnelles.
	L'Ã©noncÃ© suivant est-il une tautologie?
$
(p \Rightarrow q) \lor p \lor r \Rightarrow q \lor r$.
	\\ 

Q. 10. \og $A$ Ã&nbsp; moins que  $B$ \fg{} 
peut-elle Ãªtre reprÃ©sentÃ©e par $ B \Rightarrow A $?
	\\ 

Q. 11.  L'affirmation \og il fait beau aujourd'hui  donc il ne pleuvra pas dans dix jours \fg{}
est-elle une proposition?
	\\ 

Q. 12. 
Soit la dÃ©monstration  syntaxique suivante: \newline
\begin{center}
\begin{tabular}{lll}
\multicolumn{3}{l}{DÃ©monstration sous hypothÃ¨ses 
$\{\neg B \Rightarrow \neg A, A\}$}\\
1.&amp;$\neg B \Rightarrow \neg A$ &amp;$H_1$ \\
2.&amp;$A$ &amp;$H_2$ \\
3.&amp;\_\_\_\_\_ &amp;\_\_\_\_\_ \\
4.&amp;\_\_\_\_\_ &amp;\_\_\_\_\_ \\
5.&amp;$\neg\neg B$ &amp;rÃ©duction de l'absurde entre 4. et 1. \\
6.&amp;$\neg \neg B \Rightarrow B $&amp;Axiome 9 ($B/P$).\\
7.&amp; $B$ &amp;mp entre 5. et 6.\\
Conclusion
\end{tabular}
\end{center}

\noindent La dÃ©monstration est correcte si en 3. et 4. on a: \newline
\begin{tabular}{lll}
3.&amp;$ (\neg B \Rightarrow \neg A )\Rightarrow (\neg \neg A \Rightarrow  \neg \neg B) $ &amp;thÃ©oreme de la contraposÃ©e ($\neg B/P, \neg A /Q$) \\
4.&amp;$\neg \neg A \Rightarrow A $ &amp;Axiome 9 ($A/P $).
\end{tabular}
\\ 

Q. 13. \og $A$ Ã&nbsp; moins que  $B$ \fg{} 
peut-elle Ãªtre reprÃ©sentÃ©e par $ B \lor A $?
	\\ 

Q. 14. \og Il est faux que sa mÃ¨re est anglaise ou que son pÃ¨re est franÃ§ais \fg{}
est-elle suffisante pour affirmer que
\og sa mÃ¨re est anglaise ou  son pÃ¨re n'est pas franÃ§ais \fg{}?
	\\ 

Q. 15. 
Soit la dÃ©monstration  syntaxique suivante: \newline
\begin{center}
\begin{tabular}{lll}
\multicolumn{3}{l}{DÃ©monstration sous hypothÃ¨ses 
$\{\neg B \Rightarrow \neg A, A\}$}\\
1.&amp;$\neg B \Rightarrow \neg A$ &amp;$H_1$ \\
2.&amp;$A$ &amp;$H_2$ \\
3.&amp;\_\_\_\_\_ &amp;\_\_\_\_\_ \\
4.&amp;\_\_\_\_\_ &amp;\_\_\_\_\_ \\
5.&amp;$\neg\neg B$ &amp;rÃ©duction de l'absurde entre 4. et 1. \\
6.&amp;$\neg \neg B \Rightarrow B$ &amp;Axiome 9 ($B/P$).\\
7.&amp; $B$ &amp;mp entre 5. et 6.\\
Conclusion
\end{tabular}
\end{center}

\noindent Si elle Ã©tait complÃ¨te cela permetrait de
dÃ©montrer syntaxiquement
$(\neg B \Rightarrow \neg A) \Rightarrow (A \Rightarrow B)
$.
 L'assertion proposÃ©e est vraie ou fausse ?
\\ 

Q. 16.  L'affirmation \og le Vesuve a ravagÃ© la ville de Pompei en 1999 \fg{}
est-elle une proposition?
	\\ 

Q. 17. \og $B$ seulement si  $A$ \fg{}
peut-elle Ãªtre reprÃ©sentÃ©e par $ \neg A \Rightarrow B $?
	\\ 

Q. 18. Une formule propositionnelle $F$ est consÃ©quence logique d'une tautologie.
	 L'affirmation suivante est-elle vraie:
\og  $F$ est donc une antilogie \fg{}?
        \\ 

Q. 19.  Soit $p$, $q$, $r$ trois variables propostionnelles.
	L'Ã©noncÃ© suivant est-il une tautologie?
$(p \lor q) \land r \Rightarrow (p \lor r) \land (q \lor r)$.
	\\ 

Q. 20.  La nÃ©gation de \og ce triangle est rectangle donc ce triangle possÃ¨de un angle droit \fg{}
est-elle  \og ce triangle n'est pas rectangle donc ce triangle ne possÃ¨de pas un angle droit \fg{} ?
	\\ 

Q. 21.  Soit $p$ et $q$, deux variables propostionnelles.
	L'Ã©noncÃ© suivant est-il une tautologie?
$
(p \land ( p \lor q)) \Leftrightarrow p$.
	\\ 

Q. 22. Une formule propositionnelle $F$ a pour consÃ©quence logique une tautologie.
	 L'affirmation suivante est-elle vraie:
\og  $F$ est donc une antilogie \fg{}?
        \\ 

Q. 23. Une formule propositionnelle $F$ est consÃ©quence logique d'une antilogie.
	 L'affirmation suivante est-elle vraie:
\og  $F$ est donc une antilogie \fg{}?
        \\ 

Q. 24. 
\og \emph{Si la paix survient, alors il y aura une crise Ã©conomique
Ã&nbsp; moins que le pays se dote d'armes nouvelles ou bien exÃ©cute
un large programme d'investissement intÃ©rieur dans les secteurs de
l'enseignement, de la santÃ© et de la lutte contre la pauvretÃ©.
Il n'est pas possible de se mettre d'accord sur les objectifs
que peut se donner un large programme d'investissement intÃ©rieur.
Donc si la paix survient et qu'il n'y a pas de crise Ã©conomique,
le pays doit se doter d'armes nouvelles.} \fg{}
	 Le raisonnement proposÃ© est-il correct?
        \\ 

Q. 25. Une formule propositionnelle $F$ a pour consÃ©quence logique une tautologie.
	 L'affirmation suivante est-elle vraie:
\og  $F$ est donc une tautologie \fg{}?
        \\ 

Q. 26. \og Il est faux que sa mÃ¨re est anglaise ou que son pÃ¨re est franÃ§ais \fg{}
est-elle Ã©quivalente Ã&nbsp;
\og sa mÃ¨re est anglaise ou son pÃ¨re n'est pas franÃ§ais \fg{}?
	\\ 

Q. 27. Une formule propositionnelle $F$ a pour consÃ©quence logique une tautologie.
	 L'affirmation suivante est-elle vraie:
\og  On ne peut donc rien dire de $F$ \fg{}?
        \\ 

Q. 28. Une formule propositionnelle $F$ est consÃ©quence logique d'une tautologie.
	 L'affirmation suivante est-elle vraie:
\og  $F$ est donc une tautologie \fg{}?
        \\ 

Q. 29.  Soit $p$, $q$, $r$ trois variables propostionnelles.
	L'Ã©noncÃ© suivant est-il une tautologie?
$(p \lor q) \land r \Leftarrow (p \lor r) \land (q \lor r)$.
	\\ 

Q. 30. Une formule propositionnelle $F$ est consÃ©quence logique d'une tautologie.
	 L'affirmation suivante est-elle vraie:
\og  On ne peut donc rien dire de $F$ \fg{}?
        \\ 

\section{DÃ©duction syntaxique}

Dans le systÃ¨me \og PR \fg{} et en se servant Ã©ventuellement des thÃ©orÃ¨mes 
dÃ©jÃ&nbsp; dÃ©montrÃ©s dans le cours, dÃ©montrer syntaxiquement 
les deux formules propositionnelles suivantes:
\begin{enumerate}
\item
$
  (A \Rightarrow B) \Rightarrow 
  ((A \Rightarrow C) \Rightarrow (A \Rightarrow B \land C))
$

\item 
$
(A \Rightarrow B) \Rightarrow 
((C \Rightarrow \neg B) \Rightarrow  (A \Rightarrow \neg C))
$
\end{enumerate}

\section{ConsÃ©quences logiques}
Pour chacun des raisonnements suivants, 
\begin{itemize}
\item rÃ©Ã©crire le problÃ¨me dans une  logique  propositionnelle;
\item dire si la conclusion est une consÃ©quence logique des hypothÃ¨ses en justifiant.
\end{itemize}

\begin{enumerate}
\item Si je n'Ã©tudie pas, j'ai des remords. 
  Mais si je ne vis pas Ã&nbsp; fond ma jeunesse, j'ai aussi des remords. 
  Or je n'ai pas de remords. 
  C'est donc que j'Ã©tudie tout en vivant Ã&nbsp; fond ma jeunesse.
\item Si Jean n'a pas rencontrÃ© Pierre l'autre nuit, 
c'est que Pierre est le meurtrier ou que Jean est un menteur.
Si Pierre n'est pas le meurtrier, alors Jean n'a pas rencontrÃ© Pierre 
l'autre nuit et le crime a eu lieu aprÃ¨s minuit.
Si le crime a eu lieu aprÃ¨s minuit, alors Pierre est 
le meurtrier ou Jean n'est pas un menteur.
Donc Pierre est le meurtrier
\end{enumerate}

\section*{Annexes : Axiomes de PR}

\begin{itemize}\item Axiome 1 : $P\imp (Q\imp P)$
\item Axiome 2 : $(P\imp Q)\imp((P\imp(Q
\imp R))\imp (P\imp R))$
\item Axiome 3 : $P\imp(Q\imp P\et Q)$
\item Axiome 4 : $P\et Q\imp P$
\item Axiome 5 : $P\et Q\imp Q$
\item Axiome 6 : $P\imp P\ou Q$
\item Axiome 7 : $Q\imp P\ou Q$
\item Axiome 8: $(P\imp R)\imp((Q\imp R) \imp(P\ou Q\imp R))$
\item Axiome 9: $\non\non P\imp P$
\item Axiome 10: $(P\imp Q)\imp((P\imp\non Q)$
\item Axiome 11 : $(P\imp Q)\imp((Q\imp P)\imp(P\eqv Q))$
\item Axiome 12 : $(P\eqv Q)\imp(P\imp Q)$
\item Axiome 13 : $(P\eqv Q)\imp(Q\imp P)$
\end{itemize}



\section*{RÃ©ponses au QCM}

\begin{large}
\begin{center}
\begin{tabular}{|l|c|c||l|c|c||l|c|c|}
\hline
NumÃ©ro &amp; V &amp; F &amp; NumÃ©ro &amp; V &amp; F &amp; NumÃ©ro &amp; V &amp; F \\ 
\hline
Q. 1 &amp; &amp;  &amp; Q. 2 &amp; &amp;  &amp; Q. 3 &amp; &amp;  \\ 
\hline
Q. 4 &amp; &amp;  &amp; Q. 5 &amp; &amp;  &amp; Q. 6 &amp; &amp;  \\ 
\hline
Q. 7 &amp; &amp;  &amp; Q. 8 &amp; &amp;  &amp; Q. 9 &amp; &amp;  \\ 
\hline
Q. 10 &amp; &amp;  &amp; Q. 11 &amp; &amp;  &amp; Q. 12 &amp; &amp;  \\ 
\hline
Q. 13 &amp; &amp;  &amp; Q. 14 &amp; &amp;  &amp; Q. 15 &amp; &amp;  \\ 
\hline
Q. 16 &amp; &amp;  &amp; Q. 17 &amp; &amp;  &amp; Q. 18 &amp; &amp;  \\ 
\hline
Q. 19 &amp; &amp;  &amp; Q. 20 &amp; &amp;  &amp; Q. 21 &amp; &amp;  \\ 
\hline
Q. 22 &amp; &amp;  &amp; Q. 23 &amp; &amp;  &amp; Q. 24 &amp; &amp;  \\ 
\hline
Q. 25 &amp; &amp;  &amp; Q. 26 &amp; &amp;  &amp; Q. 27 &amp; &amp;  \\ 
\hline
Q. 28 &amp; &amp;  &amp; Q. 29 &amp; &amp;  &amp; Q. 30 &amp; &amp;  \\ 
\hline
\end{tabular} 
\end{center}
\end{large}




\end{document}</pre></body></html>